There is a need for military and commercial wireless radio networks that can operate in dynamic environments while supporting high spectral efficiency with throughput guarantees and low latency. This is particularly challenging in wireless mobile ad-hoc networks (MANETs), but simultaneous use of a frequency by multiple users enabled by multiuser detection techniques can achieve these goals.
While multiuser detection (MUD) technology promises to address the need for many to share a single frequency, realizable multiuser detection systems for ad-hoc networks of handheld units do not have the computer power to perform optimal joint detection on completely random transmissions.
There is therefore a need of some kind of scheduling for maximum channel reuse to come close to fully utilizing a MUD's capabilities without overloading it. While MUD systems were designed to be able to distinguish between the different users due to the unique features of each transmission, sophisticated high level techniques for feature extraction involving maximum likelihood joint estimation of all user's signals may not be implementable on handheld devices. This is because of the number of iterations required, the fact they must look at an entire data record; or that they require much more processing power than is available at the handheld device. Such computationally-intense algorithms include the M algorithm which is a search tree pruning algorithm that searches through only M possibilities, and the MMSE, Minimum Mean Squared Error algorithm. Thus, handheld devices may for instance not be capable of adequately implementing absolute maximum likelihood probabilities.
In summary, the handheld devices do not possess the required processing power or time luxury which in the present invention is handed by a relaxation of the timing constraints. Since for mobile ad-hoc networks the constraints need to be relaxed, some scheduling is required. Moreover, for maximum channel reuse the scheduling required is not the standard interference avoidance scheduling which prohibits transmissions if there is any possibility of inference throughout multiple hops of a network. Rather, what is required is intelligent scheduling which recognizes there are some situations in which links are permitted despite some level of interference in the network.
Note for MUD-enabled mobile ad-hoc networks in which multiple devices arrive on scene there is desirably no central processing device. There is no control node and there is no heterogeneous node where one node is more capable than another. Centralized controllers are avoided so there can be no central point of failure. Rather it is desirable that individual mobile devices act independently to do scheduling.
While some level of feature extraction is possible in mobile handsets, fully optimal joint detection of all user's features is not possible. The result is that scheduling must be utilized to avoid collisions between the ad-hoc network users when too much interference is present.
Standard scheduling such as carrier sense multiple access collision avoidance or CSMA/CA scheduling only permits one user per frequency. This scheduling unnecessarily limits the number of users that can operate on the ad-hoc network. Moreover, even though conventional ad-hoc networks suffer from hidden node or exposed node problems, for MUD-enabled ad-hoc networks, hidden nodes or exposed nodes present different interference problems.
In conventional non-MUD enabled ad-hoc networks, a hidden node occurs when a node is visible from a central node, but not from other nodes communicating with the central node. This leads to difficulties in media access control. Moreover, hidden nodes in a wireless network refer to nodes which are out of range of other nodes or a collection for nodes. Thus, the hidden node problem occurs when one user can talk to a node who also in one hop can talk to another node, but the two disparately spaced nodes cannot talk to each other. Thus, they cannot hear what the other node has said. As a result, scheduling decisions might be made that conflict considering that there may be a third node in the middle.
An exposed node occurs when a node is prevented from sending packets to other nodes due to a neighboring transmitter. For MUD-enabled ad-hoc networks, the exposed node problem is complicated by the fact that multiple nodes can be transmitting to multiple receiving nodes, some of which may be hidden from different nodes within the neighborhood. Thus, the scheduling to avoid wasted channel resources becomes more complex.
As a result, in scheduling it is very important to be able to identify hidden nodes and exposed nodes so as to avoid interference and maximize channel reuse. If one does not identify hidden nodes and exposed nodes, then a bad scheduling decision will be made. This is any decision that will result in unrecoverable data or wasted channel resources.
As noted above, prior systems have utilized interference avoidance paradigms such as carrier sense multiple access schedulers so that if any user hears that the channel is being used they are precluded from using it. Thus, these schedulers are single channel schedulers only usable where one has a single user on a single frequency.
Other interference avoidance scheduling methods use RTS CTS, Request to Send, Clear to Send messages. In these systems, a request is made to reserve the channel for a certain time period. When other users on the network hear that such a reservation is being made they know they cannot transmit.
However, utilizing these techniques does not relate to MUD systems which allow multiple users to use the same channel simultaneously. What is therefore needed is a technique that will enable scheduling that permits wider resource use such that ordinarily blocked transmissions are unblocked under certain circumstances to permit communications through ignoring traditional scheduling conflicts or by rescheduling.
By way of further background, most research in MUD technology to date has focused on physical layer challenges, with little attention being paid to design of an efficient MUD scheduler and the media access control (MAC) techniques required. MUD enabled MAC for mobile ad-hoc networks appeared in the literature only recently, with the main interest related to the “fairness” of medium access. This is described by K. Kusume, et. al, “Medium Access in Spread-Spectrum Ad-hoc Networks with Multiuser Detection,” Eurasip Journal on Advances in Signal Processing, Vol. 2009; J. Zhang, et. al, “Multiuser Detection Based MAC Design for Ad-hoc Networks,” IEEE Trans. On Wireless Communications, Vol. 8, No. 4, pp. 1836-1846, April 2009; and M. Bouharras, et. al, “Scheduling Optimization in Multiuser detection based MAC design for Networks,” IEEE LCN, Montreal, Canada, October 2008. These techniques do not relate to resource allocation, or scheduling. Without effective scheduling, the MUD's potential cannot be fully realized.
In general, the application of scheduling schemes developed in the conventional interference avoidance paradigm is not straight forward when applied to MUD enabled networks. This is discussed in F. Borgonovo, et. al, “ADHOC MAC: a new, flexible and reliable MAC architecture for ad-hoc networks,” IEEE WCNC, New Orleans, La., March 2003. Simply utilizing the above schemes in each attribute of the virtual channel may violate other requirements specific to multiuser detection.
It will be noted that the DARPA Interference Multiple Access (DIMA) communications program sought to develop a real-time prototype communication system that exploited MUD techniques to allow multiple simultaneous transmissions. Furthermore, the DIMA system was designed to operate in an ad-hoc fashion without requiring infrastructure or central controllers. Nor does the DIMA system rely on GPS. It was shown that the DIMA system can maintain a packet error rate (PER) of less than 1% as described by Y. Eisenberg, et. al, “MUD Enabled Media Access Control for High Capacity, Low-latency Spread Spectrum Communications,” IEEE MILCOM, Orlando, Fla., October 2007 and R. Learned, et. al, “Interference Multiple Access Wireless Network Demonstration Enabled by Real-Time Multiuser Detection,” IEEE Radio and Wireless Symposium, Orlando, Fla., January 2008.